package com.easy.leetcode.bit;

/**
 * 260. 只出现一次的数字 III
 */
public class SingleNumber260 {
    /**
     * 分治法
     * 一组数字中，有两个不相同，其余均相同，在整组进行亦或操作后，至少有一个位置上是1(因为有两个数字不相同)
     * 将异或后的数字，与取反后的数字进行与操作，就能得到最后一个1出现的数字，
     * 以该位置上的数字分组，分别进行亦或，就能得到两个出现一次的数字了
     * @param nums
     * @return
     */
    public int[] singleNumber(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            ans=ans^num;
        }
        ans =ans&-ans;
        int[] res =new int[2];
        for (int num : nums) {
            if ((num&ans)==0){
                res[0]=res[0]^num;
            }else {
                res[1]=res[1]^num;
            }
        }
        return res;
    }
}
